#include <stdio.h>
#include <stdlib.h>

// ---------------------------------------------
// Data Structure: Circular Queue Implementation
// ---------------------------------------------

/**
 * @brief A struct representing a circular queue.
 * @param items Pointer to the array holding the queue elements.
 * @param front The index of the front element.
 * @param rear The index of the rear element.
 * @param capacity The maximum capacity of the queue.
 */
typedef struct {
    int* items;
    int front;
    int rear;
    int capacity;
} CircularQueue;

/**
 * @brief Creates and initializes a new circular queue.
 * @param capacity The maximum number of elements the queue can hold.
 * @return A pointer to the newly created CircularQueue.
 */
CircularQueue* createQueue(int capacity) {
    CircularQueue* q = (CircularQueue*)malloc(sizeof(CircularQueue));
    if (!q) {
        perror("Failed to allocate memory for queue");
        exit(EXIT_FAILURE);
    }
    q->capacity = capacity;
    q->front = -1;
    q->rear = -1;
    q->items = (int*)malloc(q->capacity * sizeof(int));
    if (!q->items) {
        perror("Failed to allocate memory for queue items");
        free(q);
        exit(EXIT_FAILURE);
    }
    return q;
}

/**
 * @brief Checks if the queue is full.
 * @param q Pointer to the queue.
 * @return 1 if full, 0 otherwise.
 */
int isFull(CircularQueue* q) {
    return ((q->rear + 1) % q->capacity == q->front);
}

/**
 * @brief Checks if the queue is empty.
 * @param q Pointer to the queue.
 * @return 1 if empty, 0 otherwise.
 */
int isEmpty(CircularQueue* q) {
    return (q->front == -1);
}

/**
 * @brief Adds an element to the rear of the queue.
 * @param q Pointer to the queue.
 * @param value The integer value to add.
 */
void enqueue(CircularQueue* q, int value) {
    if (isFull(q)) {
        printf("Error: Queue is full\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % q->capacity;
    q->items[q->rear] = value;
}

/**
 * @brief Removes and returns the element from the front of the queue.
 * @param q Pointer to the queue.
 * @return The value of the front element.
 */
int dequeue(CircularQueue* q) {
    int element;
    if (isEmpty(q)) {
        printf("Error: Queue is empty\n");
        return -1;
    }
    element = q->items[q->front];
    if (q->front == q->rear) {
        // Queue has only one element, so we reset it after dequeing
        q->front = -1;
        q->rear = -1;
    } else {
        q->front = (q->front + 1) % q->capacity;
    }
    return element;
}

/**
 * @brief Frees the memory allocated for the queue.
 * @param q Pointer to the queue.
 */
void freeQueue(CircularQueue* q) {
    if (q) {
        free(q->items);
        free(q);
    }
}

// ---------------------------------------------
// Pascal's Triangle Logic
// ---------------------------------------------

/**
 * @brief Generates and prints Pascal's triangle up to a specified number of rows.
 *
 * This function uses a circular queue to generate each row from the previous one.
 * A '0' is used as a delimiter in the queue to mark the end of a row's data.
 * The next row is generated by calculating the sum of adjacent elements from the
 * previous row. For a row like [1, 2, 1], we can imagine it as [0, 1, 2, 1, 0]
 * to generate the sums for the next row: (0+1), (1+2), (2+1), (1+0) -> [1, 3, 3, 1].
 *
 * @param numRows The number of rows of the triangle to print.
 */
void printPascalsTriangle(int numRows) {
    if (numRows <= 0) {
        printf("Number of rows must be a positive integer.\n");
        return;
    }

    // Capacity needs to accommodate all elements of a row plus the delimiter.
    // numRows + 2 is a safe capacity.
    CircularQueue* q = createQueue(numRows + 2);

    // --- Handle Row 1 ---
    printf("1");
    if (numRows == 1) {
       printf("\n");
       freeQueue(q);
       return;
    }
    enqueue(q, 1);
    enqueue(q, 0); // Use 0 as a delimiter for the end of a row

    // --- Generate and print subsequent rows ---
    for (int i = 2; i <= numRows; i++) {
        printf("\n");
        int prev = 0;

        // Loop to generate one row
        while (1) {
            int current = dequeue(q);
            int sum = prev + current;

            // When current is 0, we've processed all data for the previous row
            if (current == 0) {
                // The sum (prev + 0) gives the last '1' of the new row
                printf("%d", sum);
                enqueue(q, sum);   // Enqueue the last '1'
                enqueue(q, 0);     // Enqueue the new delimiter
                break; // Exit the loop for this row
            } else {
                // This is the first or a middle element of the row
                printf("%d ", sum);
                enqueue(q, sum);
                prev = current;
            }
        }
    }
    printf("\n");
    freeQueue(q);
}

// ---------------------------------------------
// Main Function
// ---------------------------------------------

int main() {
    int n;
    printf("Enter the number of rows for Pascal's triangle: ");
    scanf("%d", &n);

    printf("\nPascal's Triangle (%d rows):\n", n);
    printPascalsTriangle(n);

    return 0;
}

